/*
 * @lc app=leetcode.cn id=82 lang=java
 *
 * [82] 删除排序链表中的重复元素 II
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {

    /**
     * 一次遍历
     * 
     * Accepted
    166/166 cases passed (0 ms)
    Your runtime beats 100 % of java submissions
    Your memory usage beats 88.3 % of java submissions (40.8 MB)
     */
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy, cur = head;
        while (cur != null) {
            if (cur.next != null && cur.next.val == cur.val) {
                int tmp = cur.val;
                cur = cur.next.next;
                while (cur != null && cur.val == tmp) {
                    cur = cur.next;
                }
                pre.next = cur;
            } else {
                pre = cur;
                cur = cur.next;
            }
        }
        return dummy.next;
    }

    /**
     * 递归
     * 
    * Accepted
    166/166 cases passed (0 ms)
    Your runtime beats 100 % of java submissions
    Your memory usage beats 24.48 % of java submissions (41.3 MB)
    */
    public ListNode deleteDuplicates1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        if (head.next.val != head.val) {
            head.next = deleteDuplicates(head.next);
            return head;
        } else {
            int del = head.val;
            head = head.next;
            while (head != null && head.val == del) {
                head = head.next;
            }
            return deleteDuplicates(head);
        }
    }
}
// @lc code=end
